COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	                          Math/CIS 280 exam
C00006 00003	
C00011 00004	**************
C00014 ENDMK
C⊗;
                          Math/CIS 280 exam

Take-home exam; due in one week (March 18, 1975).  You may use any (other) in-animate
objects to help do this exam. Collusion is not allowed.  WARNING: Go through the exam
before Thursday!  Thursday  I will answer  questions about the exam.  If you wait  to
Monday night to start work on the exam YOU WILL LOSE. 

Note: due to jury duty screw-up there will only be two exams, not three.


write the following functions or predicates 

dellst[u]         6 points
For the list u, dellst return a list of the atomic elements of u.
Examples:
	dellst[(A B C)] = (A B C)
	dellst[(A (B C) D (E))] = (A D)

Write dellst two ways: with and without a use of functional arguments.


vectoradd[u;v]    3 points
For lists u and v (assumed to be of equal length) this function this function returns
a list, each element of which is the sum of the corresponding elements in u and v. 
You may use plus[x;y] <= x+y; do with and without functional arguments.
Examples:
	vectoradd[(5 3);(2 -4)] = (7 -1)


allthesame[u]     3 points
For the  list u,  allthesame returns  T if  and only  if all  the elements  of u  are
identical. 


setdif[u;v]       3 points
For the lists, u and v, setdif returns a list consisting of all elements contained in
u and not contained in v. 
Examples:
	setdif[(5 4);()] = (5 4)
	setdif[(X 4 Y); (2 3 4)] = (X Y)
	setdif[(A B);(B C A D)] = ().

******************
Modifying the evaluator:   10 points
We have been using λ-notation as a binding mechanism for call-by-value.  We have aslo
noticed that it would  be convenient to have arguments passed into a function body in
unevaluated form (special forms, for  example).  We propose  to add a new binder,  β,
which  will be  used  in contexts  like  the  λ-notation but  the  arguments are  NOT
evaluated before they are passed into the body of the β-expression. 

Show what modifications would have to be made to our current evaluation scheme.

For example: Given, foo <=λ[x]car[x]  evaluation of foo[cons[A;B]] would give A.
What would 
   baz <= β[[x;y]cons[x;y]] give as evaluation for baz[car[A];cdr[b]]?

HINT: This problem requires understanding the questions of representation.


************
A quessing game:       5 points
what does this function do?

foo <= λ[[x] [atom[x] → x; T → cons[foo[car[x]];foo[cdr[x]]] ]

************
a problem and a question of efficiency:      11 points
Let l be a list  of length n: (l1, l2, l3,  ln). Each li is also a list  of length m.
Write  a function, aargh[l] which  is to return  that first sequence  (l1j, l2j, lnj)
whose elements are not all equal. 
For example:
	aargh[((A B C)(A C E)(A B E))] = (B C B)
	aargh[((A B C D)(A B E (1)))] = (C E)

Try to make an efficient computation. Explain the difficulties involved.

*************
And still it comes: additions to the evalautor      10 points
Write modifications to the value[e;tbl] function  which will  handle sums of  arbitrary
length. Do it two ways: with and without functional arguments. 

**************
equality on data structures         23 points
Recall that  a sequence (x1,  x2, x3, xn)  was defined as  having a  specific imposed
order: (A,  B) ≠ (B, A); and  two sequences are equal if  they are element-wise equal
and have the same length: (A, B, C) ≠ (A, B). 

A set {x1, x2,  x3, xn} on the other  hand, is defined as an  unordered collection of
elements; reptitions are not included:
    {1,2,A} = {A,2,1} = {A,2,A,1,1}

A data structure intermediate in complexity (between sets  and sequences) is a "bag".
A bag <x1, x2,  x3, xn>, has no imposed order, but may have repeated elements: 
<1, 2, 2> = <2, 1, 2> but does not equal <1, 2>. 

Notice that one  application of sequences is  the parameter-list to a  function call:
f[a1,a2, ...an].  The order of the ai's is important  and there can be repetitions (a
sequence).  FIRST QUESTION:  bags are a useful notation  for the parameter-list of  a
certain class of functions. what is this class ( 2 points). 

Pick representations for  each of these three  data structures. Write versions  of an
equality predicate which will implement the desired equality. 

equal_seq[(E,A,A,D,B,C);(A,B,D,E)] = NIL
equal_set[{E,A,A,D,B,C};{A,C,B,D,E}] = T
equal_bag[<E,A,D,A,C>;<A,C,A,D,E>] = T

points: 3 for sequences, 9 for sets, and 9 for bags.